#ifndef _ BINARY_SEARCH_TREE_HEADER
#define _ BINARY_SEARCH_TREE_HEADER

#include <iostream>

using namespace std;

class BSTNode{
public:
	int elem;
	BSTNode *left;
	BSTNode *right;

	BSTNode(int value = 0){
		elem = value;
		left = NULL;
		right = NULL;
	}
	~BSTNode(){}
};

typedef BSTNode* BST;

BSTNode* insert(BSTNode *node, int value){
	if(node == NULL){
		node = new BSTNode(value);
	}
	else if(value < node->elem){
		node->left = insert(node->left, value);
		//node = node->left;
	}
	else{
		node->right = insert(node->right, value);
		// node = node->right;
	}
	return node;
}

BSTNode* search(BSTNode *node, int value){
	if(node == NULL)
		return NULL;
	if(value == node ->elem)
		return node;
	else if(value < node->elem)
		search(node->left, value);
	else
		search(node->right, value);
}

BST createBST(int arr[], size_t size){
	if(0 == size)
		return NULL;
	BST root = new BSTNode(arr[0]);
	BST temp = root;
	for(int i = 1; i < size; i ++){
		temp = insert(temp, arr[i]);
	}
	return root;
}

void printBST(BST bst){
	if(bst){
		printBST(bst->left);
		cout << bst->elem << ", ";
		printBST(bst->right);
	}
}


/*
BSTNode::BST BSTNode::createBST(int arr[], size_t size){
	if(size <= 0)
		return NULL;
	BST root, node;
	BST it = root;
	root->elem = arr[0];

	for(int i = 1; i < size; i ++){
		it = root;

		if(it->elem < arr[i]){
			while(it->left != NULL)
				it = it->left;
		}
	}

	return root;
}
*/

#endif // _ BINARY_SEARCH_TREE_HEADER